package 左神算法.排序;

import java.util.Arrays;

/**
 * java内部常用的对象的排序算法都是基于merge sort改进的，例如tim sort
 *
 * 在java里面的对象排序通常都是要求使用的稳定排序
 *
 * N*log2N
 *
 * @Author linhao
 * @Date created in 9:11 下午 2022/1/28
 */
public class MergeSort {

    //    public static int[] arr = {1, 3, 9, 12, 4, 6, 7};
    public static int[] arr = {1, 4, 9, 4, 6, 7};

    /**
     * 在arr自身有序的情况下，将它拆解为两个部分，最终将其进行合并成一个数组，从而实现整体的一个有序性
     *
     * @param arr
     */
    public static void sort(int[] arr, int left, int right) {
        if (left == right) {
            return;
        }
        //避免出现两个int相加后出现越界的情况
        int mid = left + (right - left) / 2;
        sort(arr, left, mid);
        sort(arr, mid + 1, right);
        merge(arr, left, mid + 1, right);
    }

    public static void merge(int[] arr, int leftPtr, int rightPtr, int rightBound) {
        int mid = rightPtr;
        int[] temp = new int[rightBound - leftPtr + 1];
        int i = leftPtr;
        int j = rightPtr;
        int k = 0;
        while (i < mid && j <= rightBound) {
            temp[k++] = (arr[i] < arr[j]) ? arr[i++] : arr[j++];
        }

        while (i < mid) {
            temp[k++] = arr[i++];
        }
        while (j <= rightBound) {
            temp[k++] = arr[j++];
        }

        for (int m = 0; m < temp.length; m++) {
            arr[leftPtr + m] = temp[m];
        }
    }


    public static void printArr(int[] arr) {
        for (Integer integer : arr) {
            System.out.print(integer + " ");
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        Arrays.sort(arr);
        System.out.println(arr);
        MergeSort.sort(arr, 0, arr.length-1);
        printArr(arr);
    }
}
